package org.ala.linshen.dp;

/**
 * 给你一个 m x n 的整数矩阵 points （下标从 0 开始）。一开始你的得分为 0 ，你想最大化从矩阵中得到的分数。
 *
 * 你的得分方式为：每一行 中选取一个格子，选中坐标为 (r, c) 的格子会给你的总得分 增加 points[r][c] 。
 *
 * 然而，相邻行之间被选中的格子如果隔得太远，你会失去一些得分。对于相邻行 r 和 r + 1 （其中 0 <= r < m - 1），选中坐标为 (r, c1) 和 (r + 1, c2) 的格子，你的总得分 减少 abs(c1 - c2) 。
 *
 * 请你返回你能得到的 最大 得分。
 *
 * abs(x) 定义为：
 *
 * 如果 x >= 0 ，那么值为 x 。
 * 如果 x < 0 ，那么值为 -x 。
 *
 *
 * 示例 1：
 *
 *
 * 输入：points = [[1,2,3],[1,5,1],[3,1,1]]
 * 输出：9
 * 解释：
 * 蓝色格子是最优方案选中的格子，坐标分别为 (0, 2)，(1, 1) 和 (2, 0) 。
 * 你的总得分增加 3 + 5 + 3 = 11 。
 * 但是你的总得分需要扣除 abs(2 - 1) + abs(1 - 0) = 2 。
 * 你的最终得分为 11 - 2 = 9 。
 * 示例 2：
 *
 *
 * 输入：points = [[1,5],[2,3],[4,2]]
 * 输出：11
 * 解释：
 * 蓝色格子是最优方案选中的格子，坐标分别为 (0, 1)，(1, 1) 和 (2, 0) 。
 * 你的总得分增加 5 + 3 + 4 = 12 。
 * 但是你的总得分需要扣除 abs(1 - 1) + abs(1 - 0) = 1 。
 * 你的最终得分为 12 - 1 = 11 。
 *
 *
 * 提示：
 *
 * m == points.length
 * n == points[r].length
 * 1 <= m, n <= 105
 * 1 <= m * n <= 105
 * 0 <= points[r][c] <= 105
 *
 * @author ala
 * @date 2024-09-24 13:16
 */
public class Q1937 {

    public static void main(String[] args) {
        Q1937 q = new Q1937();

//        int[][] points = {{1,2,3},{1,5,1},{3,1,1}};
//        int[][] points = {{1,5},{2,3},{4,2}};
        int[][] points = {{10,8,8,9,5,7,9,8},{6,8,7,2,7,7,4,3},{10,4,8,7,10,3,4,7},{1,4,3,4,5,5,8,1},{2,2,3,6,2,3,1,6},{6,5,8,7,6,0,3,6}};

        System.out.println(q.maxPoints(points));
    }

    public long maxPoints(int[][] points) {
        return V1(points);
    }
    /**
     *  1）dp[j][0 | 1]表示：
     *      0：当前行 [0,j] 的最大得分
     *      1：当前行 [j,N-1] 的最大得分
     *      dp[j] = max(dp[i-1][k] - |j - k|) + points[i][j]
     *      把绝对值拆掉，分开讨论：
     *          k < j 时：max(dp[i-1][k] + j - k) + points[i][j]，从 j 的左边取 dp
     *                   dp[j][0] = points[i][j] - j + max(dp[i-1][k] + k)
     *          k > j 时：max(dp[i-1][k] + k - j) + points[i][j]，从 j 的右边取 dp
     *                   dp[j][1] =  points[i][j] + j + max(dp[i-1][k] - k)
     *          k = j 时：dp[i-1][j] + points[i][j]
     *  2）过程中记录下最大的dp
     */
    protected long V1(int[][] points) {
        int M = points.length, N = points[0].length;

        //  记录
        long[][] dp = new long[N][2];
        long res = 0;
        long[] L = new long[N],
               R = new long[N];
        for (int j = 0 ; j < N ; j++) {
            dp[j][0] = points[0][j] + j;
            dp[j][1] = points[0][j] - j;
            res = Math.max(res, points[0][j]);
        }
        maxLR(dp, L, R);
        if (M == 1) {return res;}

        for (int i = 1 ; i < M ; i++) {
            for (int j = 0 ; j < N ; j++) {
                long v = points[i][j];
                v = Math.max(v - j + L[j], v + j + R[j]);
                res = Math.max(res, v);

                dp[j][0] = v + j;
                dp[j][1] = v - j;
            }
            maxLR(dp, L, R);
        }
        return res;
    }
    protected void maxLR(long[][] dp, long[] L, long[] R) {
        long lm = Integer.MIN_VALUE, rm = Integer.MIN_VALUE;
        for (int i = 0 ; i < dp.length ; i++) {
            lm = Math.max(lm, dp[i][0]);
            L[i] = lm;

            int j = dp.length - 1 - i;
            rm = Math.max(rm,dp[j][1]);
            R[j] = rm;
        }
    }

}
